package writtenTraining.day27;

import java.util.*;

/**
 * day27(1)：组合数学
 */
public class Main {
    public static void main(String[] args) {
//        组合数学
//         输入数据
        Scanner in = new Scanner(System.in);
        int diff = in.nextInt(), n = in.nextInt();
        
        int ret = diff;
        for(int i = 1; i < n; i++) {
            ret *= (diff - 1);
            ret %= 109;
        }
        
        // 输出结果
        System.out.println(ret % 109);
    }
}


/**
 * day27(2)：广搜 + 剪枝：AB20 走迷宫
 */


class Main1 {
    public static void main(String[] args) {
        // 广搜 + 剪枝

        // 输入数据
        Scanner in = new Scanner(System.in);
        int row = in.nextInt(), col = in.nextInt();
        int begini = in.nextInt() - 1, beginj = in.nextInt() - 1;
        int endi = in.nextInt() - 1, endj = in.nextInt() - 1;
        char[][] str = new char[row][col];

        for(int i = 0; i < row ; i++) {
            str[i] = in.next().toCharArray();
        }

        // 进行 bfs
        boolean[][] path =new boolean[row][col];
        Queue<int[]> queue = new LinkedList<>();
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};

        // 初始化
        queue.add(new int[]{begini,beginj});
        path[begini][beginj] = true;


        // 判断是否为空
        int ret = 0;
        while(!queue.isEmpty()) {
            ret++;
            int sz = queue.size();
            for(int i =0; i < sz; i++) {
                int[] index = queue.poll();
                for(int k =0; k < 4; k++) {
                    int x = index[0] + dx[k];
                    int y = index[1] + dy[k];
                    if(x >= 0 && x < row
                            && y >= 0 && y < col
                            && str[x][y] == '.'
                            && !path[x][y]) {
                        // 如果存在结果就直接返回
                        if(x == endi && y == endj) {
                            System.out.println(ret);
                            return;
                        }
                        queue.add(new int[]{x,y});
                        path[x][y] = true;
                    }
                }
            }
        }

        // 如果不存在结果就直接输出 -1
        System.out.println(-1);
    }



}

/**
 * day27(3):贪心 + 堆：NC147 主持人调度（二）
 */

 class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // 堆 + 贪心
        int ret = 0;

        // 建立以左区间为小根堆
        // 相等时右区间为大根堆
        Arrays.sort(startEnd,((a,b)-> ((Integer)a[0]).compareTo((Integer)b[0])));
        // 存储右端点
        // 建立小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->a.compareTo(b));

        // 入队列
        queue.add(startEnd[0][1]);


        // 更新队列
        // 让 >= 最小结束时间的更新
        // 并且加入 < 的结束时间
        for(int i = 1; i < n; i++) {
            int endNum = queue.poll();
            if(startEnd[i][0] >= endNum) {
                // 如果 >= 结束时间点，刚好接上
                queue.add(startEnd[i][1]);
            } else {
                // 如果小于结束时间点，就加入新的
                queue.add(endNum);
                queue.add(startEnd[i][1]);
            }

        }

        return queue.size();
    }
}